This invention relates generally to image processing and, more particularly, to techniques for compressing the digital representation of a document.
Documents scanned at high resolutions require very large amounts of storage space. Instead of being stored as is, the data is typically subjected to some form of data compression in order to reduce its volume, and thereby avoid the high costs associated with storing it. xe2x80x9cLosslessxe2x80x9d compression methods such as Lempel-Ziv Welch (LZW) do not perform particularly well on scanned pixel maps. While xe2x80x9clossyxe2x80x9d methods such as JPEG work fairly well on continuous-tone pixel maps, they do not work particularly well on the parts of the page that contain text. To optimize image data compression, techniques, which can recognize the type of data being compressed, are needed.
One approach to satisfy the compression needs of differing types of data has been to use a document image representation which employs a Mixed Raster Content (MRC) format to describe the image. The imagexe2x80x94a composite image having text intermingled with color or gray scale informationxe2x80x94is segmented into two or more planes, generally referred to as the upper and lower plane, and a selector plane is generated to indicate, for each pixel, which of the image planes contains the actual image data that should be used to reconstruct the final output image. Segmenting the planes in this manner can improve the compression of the image because the data can be arranged such that the planes are smoother and more compressible than the original image. Segmentation also allows different compression methods to be applied to the different planes, thereby allowing a compression technique that is most appropriate for the data residing thereon can be applied to each plane.
An approach such as this is discussed in U.S. Pat. No. 5,778,092 to MacLeod et al. issued Jul. 7, 1998, the contents of which are hereby incorporated by reference. MacLeod et al. discloses a technique for compressing a color or gray scale pixel map that represents a document. The pixel map is decomposed into a three-plane representationxe2x80x94a reduced-resolution foreground plane, a reduced-resolution background plane, and a high-resolution binary selector plane. The foreground plane contains the color or gray scale information of foreground items such as text. The background plane contains the color or gray scale information for the xe2x80x9cbackgroundxe2x80x9d of the page and the continuous tone pictures that are contained on the page. The selector plane stores information for selecting from either the foreground plane or background plane during decompression.
The present invention is directed to segmenting color image data using the MRC format. Edges are generally defined as sharp discontinuities between regions of two constant colors or large sections of light intensity values. Here, edges of the image are separated into two portions. The foreground layer generally contains information about the darker sides, while the background layer contains the information about the smooth regions of the image and the brighter sides of the edges. Segmentation is performed by sectioning the image into stripes and (where the height of each stripe is equal to the size of the block) and processing each stripe block by block from the top of the image to the bottom.
The following disclosures may be relevant to aspects of the present invention:
U.S. Pat. No. 5,251,271 to Fling issued Oct. 5, 1993 discloses a method for registering digitized multi-plane color images. The method designates one plane as the reference plane and registers each of the other warped planes with the reference plane. Each plane comprises pixels representing luminosity values having scalar x and y coordinates representing positions in the horizontal and vertical directions, respectively, of the plane. The planes are divided into regions. Correlation values are calculated for regions within the divisional region of the reference plane with a plurality of regions offset from the corresponding warped divisional region. A warp error value is calculated for each pixel of each divisional region as a function of the scalar offset. The warp error values are interpolated and added to the current position of each pixel of the warped plane.
Separate processing of various types of data contained in a document is disclosed in U.S. Pat. No. 5,060,980 to Johnson et al. issued Oct. 29, 1991 which describes a xe2x80x9cformxe2x80x9d that includes user modifiable fields and an encoded description of the location, size, type, etc. of the fields to allow for direct programming of a form interpreter. Other information including the processing of the form, encoded data, etc. may be included in the encoded information. A system for creating forms carrying an encoded description of selected attributes of the fields includes means for selecting or creating fields and locating the fields on a form while generating, substantially simultaneously, the encoded description of the selected attributes. A form composer then allows merging of the form and its encoded description for printing or electronic transmission. A system for reading such forms includes a scanner, decoding device, and processor. By reading such forms, data may be entered into or recalled from a data processing system, or a form interpreter may be programmed, locally or remotely, for subsequent handling of forms.
U.S. Pat. No. 5,784,175 to Lee, issued Jul. 21, 1998 discloses a video compression encoder process for compressing digitized video signals representing display motion in video sequences of multiple image frames. The encoder process utilizes object-based video compression to improve the accuracy and versatility of encoding interframe motion and intraframe image features. Video information is compressed relative to objects of arbitrary configurations, rather than fixed, regular arrays of pixels as in conventional video compression methods. This reduces the error components and thereby improves the compression efficiency and accuracy. As another benefit, object-based video compression of this invention provides interactive video editing capabilities for processing compressed video information.
U.S. Pat. No. 5,303,313 to Mark et al. issued Apr. 12, 1994 describes image compression based on symbol matching. An image is xe2x80x9cpre-compressedxe2x80x9d prior to symbol matching using run-length encoding. Symbols are then extracted from the run-length representation. A voting scheme is used in conjunction with a plurality of similarity tests to improve symbol-matching accuracy. A template composition scheme wherein the template may be modified based on symbol matches is also disclosed.
U.S. Pat. No. 5,432,870 to Schwartz issued Jul. 11, 1995 discloses a method and apparatus for compressing and decompressing images of documents. More specifically, a method and apparatus for compressing images having a binary extractor, a binary compressor and a JPEG compressor is disclosed. The binary extractor produces a binary image representing an estimate of the binary information in the original image. The binary compressor compresses the binary image. The binary image is also subtracted from the original image to produce a difference image representing the continuous-tone information in the original image. The difference image is then compressed using the JPEG compressor. In this manner, the present invention compresses a document image without having to perform segmentation on the image.
Pending U.S. Patent Application by Fan et al. identified as Ser. No. 09/203,870 entitled Method and Apparatus for Segmenting Data to Create Mixed Raster content Planes and assigned to the assignee of the present invention discloses a technique for compressing a color or gray scale pixel map representing a document using an MRC format includes a method of segmenting an original pixel map into two planes, and then compressing the data or each plane in an efficient manner. The image is segmented by separating the image into two portions at the edges. One plane contains image data for the dark sides of the edges, while image data for the bright sides of the edges and the smooth portions of the image are placed on the other plane. This results in improved image compression ratios and enhanced image quality.
Concurrently filed U.S. Patent Application by DeQueiroz et al. identified as Ser. No. 09/206,487 entitled Method and Apparatus for Pre-Processing Mixed Raster Content Planes to Improve the Quality of a Decompressed Image and Increase Document Compression Ratios and assigned to the assignee of the present invention discloses a technique for compressing a color or gray scale pixel map representing a document is disclosed. The pixel map is decomposed into a three-plane representation, a reduced-resolution xe2x80x9cupperxe2x80x9d plane, a reduced-resolution xe2x80x9clowerxe2x80x9d plane, and a high-resolution binary selector plane. The xe2x80x9cupperxe2x80x9d and xe2x80x9clowerxe2x80x9d planes contain the color or gray scale for the page as well as the continuous tone pictures that are contained on the page. The selector plane stores information for selecting from either the foreground plane or background plane during decompression. Information contained in the selector plane is first used to pre-process the upper and lower planes to reduce the amount of data on each of the other two planes that will be subjected to further processing. Each of the pre-processed planes is compressed using a compression technique optimal for the type of data that resides upon it.
Concurrently filed U.S. Patent Application by DeQueiroz et al. identified as entitled Iterative Smoothing Technique for Pre-processing Mixed Raster Content Planes to Improve the Quality of a Decompressed Image and Increase Document Compression Ratios and assigned to the assignee of the present invention discloses a method and apparatus for compressing a mixed raster content image that represents a color or gray scale a document is disclosed. The pixel map is decomposed into a three-plane representationxe2x80x94a reduced-resolution xe2x80x9cupperxe2x80x9d plane, a reduced-resolution xe2x80x9clowerxe2x80x9d plane, and a high-resolution binary selector plane. An iterative smoothing technique is then used to pre-process the upper and lower planes using the information contained in the selector plane, thereby reducing the amount of data that will be subjected to further processing.
Concurrently filed U.S. Patent Application by Klassen et al. identified as entitled Method and Apparatus for Segmenting a Composite Image Into Mixed Raster Content Planes, and assigned to the assignee of the present invention discloses a technique for compressing a color or gray scale pixel map representing a document using an MRC format including a method of segmenting an original pixel map into two planes, and then compressing the data or each plane in an efficient manner. The image is segmented such that pixels that compress well under a lossy compression technique are placed on one plane and pixels that must be compressed losslessly are placed on another plane. Lossy compression is then applied to the lossy pixel plane while lossless compression is applied to the lossless pixel plane.
All of the references cited herein are incorporated by reference for their teachings.
Accordingly, although known apparatus and processes are suitable for their intended purposes, a need remains for a method and apparatus that can efficiently process digital image data by separately compressing the various portions of a composite image.
In one embodiment, the present invention discloses a method of segmenting digital image data for mixed raster content processing, which includes: acquiring a block of the digital image data, wherein the digital image data is composed of light intensity signals in discrete locations; calculating a threshold value for the block; and generating a selector block which indicates which of the light intensity signals exceeds the threshold value and which of the light intensity signals is below the threshold value.